/**
 * FileName: Heap
 * Author:   powersi
 * Date:     2021/1/8 16:42
 * Description: heap
 */
package com.zm.demo.core.leetcode.heap;

import java.util.Arrays;

/**
 * Description: heap
 * Author:      powersi
 * Date:        2021/1/8 16:42
 */
public class DynamicHeap {

    public Integer[]a; //数组，从1开始
    public int count; //已存储的数
    public int n; // 堆可以存储的最大数


    public DynamicHeap(int cap){
        a = new Integer[cap+1];
        n = cap;
        count = 0;
    }

    //插入
    public void insertMaxHeap(int data) {
        if (count == n) {
            n = 2*count;
            a = Arrays.copyOf(a, n);
        };
        count++;
        a[count] = data;
        int i = count;
        while (i/2 > 0 && a[i] > a[i/2]){
            swap(a, i, i/2);
            i = i/2;
        }

    }
    //插入
    public void insertMinHeap(int data) {
        if (count >= n) return;
        count++;
        a[count] = data;
        int i = count;
        while (i/2 > 0 && a[i] < a[i/2]){
            swap(a, i, i/2);
            i = i/2;
        }

    }

    private void swap(Integer[] a, int i, int parentIndex) {
        if (a[i] == null){
            return;
        }
        Integer temp = a[i];
        a[i] = a[parentIndex];
        a[parentIndex] = temp;
    }

    //删除
    public void delete(int pos) {
        a[pos] = a[count];
        a[count--] = null;

        heapily(a, pos, 2*pos);
    }

    //删除
    public void delete1(int pos) {
        a[pos] = a[count];
        a[count--] = null;
        heapily1(a, pos, 2*pos);
    }

    private void heapily(Integer[] a, int pos, int left) {
        if (left > count){
            return;
        }
        if (a[left] == null || a[pos] <= a[left]){
            swap(a, left, pos);
            heapily(a, left, 2*left);
        }else if (a[left+1] == null || a[pos] <= a[left+1] ){
            swap(a, left+1, pos);
            heapily(a, left+1, 2*(left+1));
        }
    }

    private void heapily1(Integer[] a, int parentIndex, int leftIndex) {
        while (2*parentIndex <= count){
            leftIndex = 2*parentIndex;
            if (a[leftIndex] == null || a[parentIndex] <= a[leftIndex]){
                swap(a, leftIndex, parentIndex);
                parentIndex = leftIndex;
            }else if (a[leftIndex+1] == null || a[parentIndex] <= a[leftIndex+1]){
                swap(a, leftIndex+1, parentIndex);
                parentIndex = leftIndex+1;
            }
        }

    }

    //排序
    public void sort(int i) {
    }
}
